Writing and amending algorithms

Objectives : Student should be able to -

Q1.  Describe different stages of designing and constructing an algorithm.

  1. Analyse the problem and make sure that you understood it properly.
  2. Determine what would be the -
  3. Break down the problem into sub-problems if it is complex.
  4. Write down all the steps needed to solve the problem sequentially from start to end.
  5. Determine what variables and constants need to be declared and initialized to setup the program.
  6. Determine the sequential statements and compound statements (like, selection and looping) need to be used.
  7. Construction your algorithm using either flowchart or pseudocode designing tools.
  8. Making sure that it can be easily read and understood by others. Use meaningful names for variables and constants.
  9. Use several sets of test data (normal, abnormal and boundary) and trace tables to find any errors in your algorighm.
  10. Debug the errors if found, and test your algorithm until it works perfectly to produce the desired output.

Q2.  A school with 600 students wants to produce some information from the results of the four standard tests in Maths, Science, English and IT. Each test is out of 100 marks. The information output should be the highest, lowest and average mark for each test and the highest, lowest and average mark overall. All the marks need to be input.

a)  Use pseudocode to write the algorithm to complete this task.

// Initialisation of variables for overall counters
OverallHighest ‹— 0
OverallLowest ‹— 100
OverallTotal ‹— 0
FOR Test = 1 TO 4  // Outer loop for 4 subject tests
// Initialisation of variables for subject counters
SubjectHighest ‹— 0
SubjectLowest ‹— 100
SubjectTotal ‹— 0
CASE OF Test
1 :   SubjectName ‹— "Maths"
2 :   SubjectName ‹— "Science"
3 :   SubjectName ‹— "English"
4 :   SubjectName ‹— "IT"
ENDCASE
FOR NoStd = 1 TO 600  // Inner loop 600 times for students, for each subject
// Range check validation of marks between 0 and 100
REPEAT
OUTPUT "Enter Student-", NoStd, "'s mark for ", SubjectName
INPUT  Mark
UNTIL Mark >=0 AND Mark <= 100
// Identifying and storing subject-wise and overall highest and lowest mark
IF Mark > SubjectHighest THEN SubjectHighest ‹— Mark
IF Mark > OverallHighest THEN OverallHighest ‹— Mark
IF Mark < SubjectLowest THEN SubjectLowest ‹— Mark
IF Mark < OverallLowest THEN OverallLowest ‹— Mark
// Calculating and storing subject-wise and overall running total
SubjectTotal ‹— SubjectTotal + Mark
OverallTotal ‹— OverallTotal + Mark
NEXT NoStd
// Calculate and output subject-wise average, highest and lowest mark
SubjectAverage ‹— SubjectTotal / 600
OUTPUT SubjectName
OUTPUT "Average mark is ", SubjectAverage
OUTPUT "Highest mark is ", SubjectHighest
OUTPUT "Lowest mark is ", SubjectLowest
NEXT  Test
// Calculate and output overall average, highest and lowest mark
OverallAverage ‹— OverallTotal / 2400
OUTPUT "Overall Average mark is ", OverallAverage
OUTPUT "Overall Highest mark is ", OverallHighest
OUTPUT "Overall Lowest mark is ", OverallLowest

b)  Explain how you would test your algorithm.

For the algorithm to be tested by dry running, I would reduce the number of students to 5 and the number of subjects to 2.

Q3.  The 1D array StudentName[ ] contains the names of students in a class. The 2D array StudentMark[ ] contains the mark for each subject, for each student. The position of each student’s data in the two arrays is the same, for example, the student in position 10 in StudentName[ ] and StudentMark[ ] is the same.

The variable ClassSize contains the number of students in the class. The variable SubjectNo contains the number of subjects studied. All students study the same number of subjects.

a)  Write pseudocode algorithm to setup and input data as follows -

// Declaring 1D and 2D array
DECLARE StudentName : ARRAY[1:100] OF STRING
DECLARE StudentMark : ARRAY[1:100, 1:10] OF INTEGER
// Declaring variables
DECLARE ClassSize : INTEGER
DECLARE SubjectNo : INTEGER
// Input number of students and subjects
OUTPUT “Enter the number of students : ”
INPUT  ClassSize
OUTPUT “Enter the number of subjects : ”
INPUT  SubjectNo
// Outer loop to repeat for each student
FOR NoStd = 1 TO ClassSize
OUTPUT “Enter the name of the student : ”
INPUT  StudentName[NoStd]
// Inner loop to repeat for each subject
FOR NoSub = 1 TO SubjectNo
OUTPUT “Enter the mark for subject-”, SNo, “ : ”
INPUT  StudentMark[NoStd, NoSub]
NEXT  NoSub
NEXT  NoStd

b)  The arrays and variables have already been set up and the data stored in part (a).

Students are awarded a grade based on their average mark.

Average mark Grade awarded
greater than or equal to 70 Distinction
greater than or equal to 55 and less than 70 Merit
greater than or equal to 40 and less than 55 Pass
less than 40 Fail

Write a program that meets the following requirements :

You must use pseudocode or program code and add comment to explain how your code works.

// Initialise constants for different grade awarded
CONSTANT Distinction = 70
CONSTANT Merit = 55
CONSTANT Pass = 40
// Initialise variables to count the number of students with different grades
NoDistinction = 0
NoMerit = 0
NoPass = 0
NoFail = 0
// Outer loop to repeat for each student of class
FOR NoStd = 1 TO ClassSize
StdTotal = 0 // Initialise variable to calculate total mark of each student
// Inner loop to repeat for each subject
FOR NoSub = 1 TO SubjectNo
// Calculate total mark of each student
StdTotal = StdTotal + StudentMark[NoStd, NoSub]
NEXT  NoSub
// Calculate and round the average mark to its nearest whole number
AverageMark = ROUND(StdTotal / SubjectNo, 0)
// Check and store the grade awarded
IF AverageMark >= Distinction THEN
GradeAwarded = “Distinction”
NoDistinction = NoDistinction + 1
ELSE
IF AverageMark >= Merit THEN
GradeAwarded = “Merit”
NoMerit = NoMerit + 1
ELSE
IF AverageMark >= Pass THEN
GradeAwarded = “Pass”
NoPass = NoPass + 1
ELSE
GradeAwarded = “Fail”
NoFail = NoFail + 1
ENDIF
ENDIF
ENDIF
// Output the student's name, total mark, average and grade awarded.
OUTPUT StudentName[NoStd], “ has score total mark ”, StdTotal
OUTPUT "Average mark ", AverageMark
OUTPUT "He is awarded with grade ", GradeAwarded
NEXT  NoStd
// Output the overall number of students awarded with different grade
OUTPUT “Number of Distinctions = ”, NoDistinction
OUTPUT “Number of Merits = ”, NoMerit
OUTPUT “Number of Passes = ”, NoPass
OUTPUT “Number of Fails = ”, NoFail

Q4.  Write an algorithm that allows to input a password and check if it contains at least eight characters. The program should ask to re-enter the password to check that both inputs are the same.

The user is allowed three attempts at inputting a password of the correct length and a matching pair of passwords.

The pre-defined function LEN(X) returns the number of characters in the string, X.

// Initialise a counter to try for 3 attempts
Attempt ‹— 0
// Loop or repeat until correct password or attempt is 3
REPEAT
// Tag a variable as TRUE
PassCheck ‹— TRUE
OUTPUT "Please enter your passowrd : "
INPUT Password
IF  LEN(Password) < 8 THEN
// Tag as FALSE, if password is less than 8 characters.
PassCheck ‹— FALSE
ELSE
OUTPUT "Please re-enter your password : "
INPUT Password2
IF Password2 < > Password THEN
// Tag as FALSE, if both password doesn't match.
PassCheck ‹— FALSE
ENDIF
ENDIF
Attempt ‹— Attempt + 1
UNTIL PassCheck OR Attempt = 3

IF PassCheck THEN
// Output success if password is valid.
OUTPUT "Password successful"
ELSE
OUTPUT "Password failed"
ENDIF

Q5.  Write an algorithm that meets the following requirements :

You must use pseudocode or program code and add comment to explain how your code works.

// Initialisation of variables by storing some password
Password ‹— "Johny4U"
// Loop or repeat until option-4 to Quit
REPEAT
// Calling procedure to display the available options
CALL DashBoard
// Ask to input the option of their choice
OUTPUT “Input the option between 1 and 4 : ”
INPUT  Option

CASE Option OF
1 :
OUTPUT “Enter your new password : ”
INPUT NewPass
Password = NewPass
OUTPUT “New password is added successfully.”
2 :
OUTPUT “Enter the password to check : ”
INPUT CheckPass
// Call the function to check both password matches
// by assigning parameter to pass and get return value
OUTPUT “Your password is ”, PassChecker(CheckPass, Password)
3 :
OUTPUT “Enter your old password : ”
INPUT OldPass
// Call the function to verify and authenticate
IF PassChecker(OldPass, Password) = “correct” THEN
OUTPUT “Enter your new password : ”
INPUT NewPass
OUTPUT “Your password is changed successfully.”
ELSE
OUTPUT “Your old password is wrong.”
ENDIF
4 :
OUTPUT “Thanks for using the program.”
OTHERWISE :
OUTPUT “Invalid, re-enter the option.”
ENDCASE
UNTIL Option = 4

// Procedure or sub-routine to display the available options.
SUB DashBoard
OUTPUT “Choose the option from the list below -”
OUTPUT “1. Enter a new password.”
OUTPUT “2. Check the password.”
OUTPUT “3. Change the password.”
OUTPUT “4. Quit.”
END SUB

// Function to check if input password matches with the current password
FUNCTION PassChecker(PassToCheck, CurrentPwd : STRING) RETURNS STRING
IF CurrentPwd = PassToCheck THEN
RETURN “correct”
ELSE
RETURN “wrong”
ENDIF
END FUNCTION

Q6.  Write an algorithm to input password and check if it is valid or not using procedure or function.

If password is invalid then output appropriate message with reason and ask to re-enter.

It should check the following about the password :

// Loop or repeat until the password is valid
REPEAT
OUTPUT "Enter the password :
INPUT Password
// Call the function to check and output if the password is valid or not.
OUTPUT PassValidatation(Password)
UNTIL PassValidatation(Password) = "Valid password."

// Function to check if the password meet all the set criteria
// and return the message whether it is valid or not with reason.
FUNCTION PassValidation(Pwd : STRING) RETURNS STRING
// Initialisation of all needed counters
NoSpace ‹— 0
NoUpCase ‹— 0
NoLowCase ‹— 0
NoDigit ‹— 0
Digits = "0123456789"
// Check if the length of password is within the range or not
IF (LENGTH(Pwd) >= 10 AND LENGTH (Pwd) < = 20) THEN
// Loop for each character of password
FOR Count = 1 TO LENGTH(Pwd)
// Check if the password contains white space and if not then, then -
IF (SUBSTRING(Pwd, Count, 1) < > “ ”) THEN
// Check if they are alphabetic letters
IF (LOWER(SUBSTRING(Pwd, Count, 1)) < > UPPER(SUBSTRING (Pwd, Count, 1))) THEN
// Check and count for Upper and Lower-case letter
IF (SUBSTRING(Pwd, Count, 1) = UPPER(SUBSTRING (Pwd, Count, 1)) THEN
NoUpCase = NoUpCase + 1
ELSE
NoLowCase = NoLowCase + 1
ENDIF
ELSE
// If not alphabets, then check if it contains numeric digits
FOR D = 1 TO LENGTH(Digits)
IF SUBSTRING(Pwd, D, 1) = SUBSTRING(Digits, D, 1) THEN NoDigit = NoDigit + 1
NEXT D
ENDIF
ELSE
// If white space then Count
NoSpace = NoSpace + 1
ENDIF
NEXT Count
// Return whether password is valid or not with appropriate reason
IF (NoSpace = 0 AND NoUpCase > 0 AND NoLowCase > 0 AND NoDigit > 0) THEN RETURN "Valid password."
IF NoSpace > 0 THEN RETURN "Invalid password, blank space is not allowed."
IF NoUpCase = 0 THEN RETURN "Invalid password, it should contain atleast one upper case letter."
IF NoLowCase = 0 THEN RETURN "Invalid password, it should contain atleast one lower case letter."
IF NoDigit = 0 THEN RETURN "Invalid password, it should contain atleast one digit between 0 and 9."
ELSE
// Return if password is less than 10 or greater than 20 characters
RETURN "Invalid password, it should be between 10 and 20 character in length."
ENDIF
END FUNCTION

Q7.  Write and test a program that uses a two-dimensional array, Game[ ] to store the moves in a noughts and crosses game.

The program should meet the following requirements :

// Declare and Initialise the Array with empty space.
DECLARE Game : ARRAY[1:3, 1:3] OF STRING
FOR Row = 1 TO 3
FOR Col = 1 TO 3
Game[Row, Col] = ""
NEXT Col
NEXT Row

// Create loop to repeat input 9-times for 3x3 different cells.
FOR Count=1 TO 9
// Input the location of move and accept only if it is empty.
REPEAT
INPUT "Enter the row : ", XAxis
INPUT "Enter the column : ", YAxis
IF (Game[ XAxis, YAxis] = “X” OR Game[XAxis, YAxis] = “O”) THEN
OUTPUT “Invalid, this place is not expty”
ENDIF
UNTIL NOT(Game[XAxis, YAxis] = “X” OR Game[XAxis, YAxis] = “O”)

// Input in turn and accept only “X” or “O”.
// Ensure that each of the player uses different symbol.
REPEAT
OUTPUT "Put nought or cross in row-", XAxis, ", Col-", YAxis
INPUT Symbol
// Storing input in upper case letter
Play = UPPER[Symbol]
IF NOT(Play = ”X” OR Play = ”O”) THEN OUTPUT “Invalid - try again ‘X’ or ‘O’ only”
// After play-1, check whether current symbol matches with previous one.
IF (Count > 1 AND Play = SymbolTag) THEN OUTPUT “Invalid, please put another symbol”
UNTIL (Play = “X” OR Play = “O”) AND (Play <> SymbolTag)
// Storing the input in ARRAY after validation
Game[XAxis, YAxis] = Play
// Store the input in temporary variable to match with the next entry
SymbolTag = Play

// Call the Procedure to output the current status of the board
Call DisplayBoard

// Call the Function to check and output the winner.
IF Result(Play) = “won” THEN
OUTPUT “Player with ”, Play, “-mark “, Result(Play), “ the game.”
// Stop the game if function returns "won", by exiting the loop
EXIT FOR
ENDIF
NEXT Count

// Procedure to output the current status of the game board
SUB DisplayBoard
FOR Row=1 TO 3
FOR Col=1 TO 3
// Semi-colon ; symbol allows to output in same line.
OUTPUT Game$(Row, Col), " " ;
NEXT Col
// PRINT breaks the line and allows to continue on next
PRINT
NEXT Row
END SUB

// Function to check who 'won' the game and
// return the result back.
FUNCTION Result(ParameterMark : STRING) RETURNS STRING
// Check for same mark in straight row
FOR Row = 1 TO 3
FOR Col = 1 TO 3
IF Game[Row, Col] = ParameterMark THEN
InRow = "True"
ELSE
InRow = "False"
ENDIF
// Exit the inner-loop if the symbols are not same and check the next row.
IF InRow = "False" THEN EXIT FOR
NEXT Col
// Exit the outer-loop altogether, if the symbols are same in the row.
IF InRow = "True" THEN EXIT FOR
NEXT Row

// Check for same mark in straight column
FOR Col = 1 TO 3
FOR Row = 1 TO 3
IF Game[Row, Col] = ParameterMark THEN
InColumn = "True"
ELSE
InColumn = "False"
ENDIF
// Exit the inner-loop if the symbols are not same and check the next column.
IF InColumn = "False" THEN EXIT FOR
NEXT Row
// Exit the outer-loop altogether, if the symbols are same in the column.
IF InColumn = "True" THEN EXIT FOR
NEXT Col

// Check for same mark in diagonal-1 (left to right)
FOR D1 = 1 TO 3
IF Game[D1, D1] = ParameterMark THEN
InD1 = "True"
ELSE
InD1 = "False"
ENDIF
IF InD1 = "False" THEN EXIT FOR
NEXT D1

// Check for same mark in diagonal-2 (right to left)
D2Col = 3
FOR D2 = 1 TO 3
IF Game[D2, D2Col] = ParameterMark THEN
InD2 = "True"
ELSE
InD2 = "False"
ENDIF
D2Col = D2Col - 1
IF InD2 = "False" THEN EXIT FOR
NEXT D2

IF (InRow = "True" OR InColumn = "True" OR InD1 = "True" OR InD2 = "True") THEN
// Returns the parameter value "won".
RETURN "won"
ENDIF
END FUNCTION


* * * * * * * * *
* * * * * *
* * *
*